/*
*
给你一个 n x n 整数矩阵 grid ，请你返回 非零偏移下降路径 数字和的最小值。

非零偏移下降路径 定义为：从 grid 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。

示例 1：

输入：grid = [[1,2,3],[4,5,6],[7,8,9]]
输出：13
解释：
所有非零偏移下降路径包括：
[1,5,9], [1,5,7], [1,6,7], [1,6,8],
[2,4,8], [2,4,9], [2,6,7], [2,6,8],
[3,4,8], [3,4,9], [3,5,7], [3,5,9]
下降路径中数字和最小的是 [1,5,7] ，所以答案是 13 。
示例 2：

输入：grid = [[7]]
输出：7

提示：

n == grid.length == grid[i].length
1 <= n <= 200
-99 <= grid[i][j] <= 99

  - @author ala
  - @date 2024-09-19 11:40
*/
package main

import (
	"fmt"
	"math"
)

func main() {
	grid := [][]int{{7}}

	fmt.Println(minFallingPathSum(grid))
}

/**
 *  1）找到第一行的 最大 和 次大，表示第一行的最大路径和 和 次大路径和
 *      mn1：本行最大路径和 mn1j：本行最大路径和所在列
 *      mn2：             mn2j：
 *  2）从第二行开始，维护每行的最大路径和 和 次大路径和
 *      dp[i][j]为：
 *      如果 j == min1j：则 dp[i][j] = mn2 + grid[i][j]
 *                      否则 dp[i][j] = mn1 + grid[i][j]
 */
func minFallingPathSum(grid [][]int) int {
	M, N := len(grid), len(grid[0])

	//  最大，次大 和 最大j，次大j
	mn1, mn2 := math.MaxInt, math.MaxInt
	mn1j := -1

	for j := 0; j < N; j++ {
		v := grid[0][j]
		if v < mn1 {
			mn2 = mn1
			mn1, mn1j = v, j
		} else if v < mn2 {
			mn2 = v
		}
	}

	for i := 1; i < M; i++ {
		_mn1, _mn1j := math.MaxInt, -1
		_mn2 := math.MaxInt
		for j := 0; j < N; j++ {
			v := grid[i][j]

			if j == mn1j {
				v += mn2
			} else {
				v += mn1
			}

			if v < _mn1 {
				_mn2 = _mn1
				_mn1, _mn1j = v, j
			} else if v < _mn2 {
				_mn2 = v
			}
		}
		mn1, mn1j = _mn1, _mn1j
		mn2 = _mn2
	}

	return mn1
}
